package org.example;

public class Test1 {
    //leetcode 968 监控二叉树 https://leetcode.cn/problems/binary-tree-cameras/description/
    /**
     * 贪心，尽量选择在叶子节点的父节点安装摄像头，这样能保证摄像头覆盖更多的节点,然后其余的就是中间隔
     * 两个节点安装摄像头
     * 分别用0，1，2表示节点的状态，0表示无摄像头覆盖，1表示该节点装摄像头，2表示有摄像头覆盖
     */
    int count;
    public int minCameraCover(TreeNode root) {
        int ret = greed(root);
        if (ret == 0) count++;
        return count;
    }

    private int greed(TreeNode root) {
        //当遇到null的时候，只有当这个null节点的状态为2的时候，才能保证叶子节点的父节点安装摄像头
        if (root == null) return 2;
        int left = greed(root.left);
        int right = greed(root.right);
        if (left == 0 || right == 0) {
            count++;
            return 1;
        }else if (left == 1 || right == 1) {
            return 2;
        }else return 0;
    }
}
